新生舞会

Time Limit: 10 Sec Memory Limit: 128 MB

Description

学校组织了一次新生舞会，Cathy作为经验丰富的老学姐，负责为同学们安排舞伴。有n个男生和n个女生参加舞会买一个男生和一个女生一起跳舞，互为舞伴。

Cathy收集了这些同学之间的关系，比如两个人之前认识没计算得出 a[i][j] ，表示第i个男生和第j个女生一起跳舞时他们的喜悦程度。

Cathy还需要考虑两个人一起跳舞是否方便，比如身高体重差别会不会太大，计算得出 b[i][j]，表示第i个男生和第j个女生一起跳舞时的不协调程度。

当然，还需要考虑很多其他问题。Cathy想先用一个程序通过a[i][j]和b[i][j]求出一种方案，再手动对方案进行微调。

Cathy找到你，希望你帮她写那个程序。

一个方案中有n对舞伴，假设没对舞伴的喜悦程度分别是a’1,a’2,…,a’n，

假设每对舞伴的不协调程度分别是b’1,b’2,…,b’n。

令C=(a’1+a’2+…+a’n)/(b’1+b’2+…+b’n),Cathy希望C值最大。

Input

第一行一个整数n。

接下来n行，每行n个整数，第i行第j个数表示a[i][j]。

接下来n行，每行n个整数，第i行第j个数表示b[i][j]。

Output

一行一个数，表示C的最大值。四舍五入保留6位小数，选手输出的小数需要与标准输出相等

Sample Input

3
　19 17 16
　25 24 23
　35 36 31
　9 5 6
　3 4 2
　7 8 9

Sample Output

5.357143

HINT

1<=n<=100,1<=a[i][j],b[i][j]<=10^4

Main idea

选择两个人<i,j>会获得A[i][j]，以及B[i][j]，选择后不能再选，要求使得ΣA[i][j]/ΣB[i][j]最大。

Solution

img

最大费用最大流的话，可以把权值取相反数，然后跑最小费用最大流。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 205;
const int EDG = 25005;
const double eps = 1e-6;
const int INF = 21474836;


int n,m;
int A[ONE][ONE],B[ONE][ONE];
int next[EDG],first[ONE],go[EDG],from[EDG],pas[EDG],tot;
int vis[ONE],q[1000001],pre[ONE],tou,wei;
double w[EDG],dist[ONE];
int S,T;
double Ans;

inline int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int Add(int u,int v,int flow,double z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  pas[tot]=flow;  w[tot]=z;   from[tot]=u;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  pas[tot]=0;     w[tot]=-z;  from[tot]=v;
}

bool Bfs()
{
    for(int i=S;i<=T;i++) dist[i]=INF;
    tou = 0;    wei = 1;
    q[1] = S;   vis[S] = 1; dist[S] = 0;
    while(tou < wei)
    {
        int u = q[++tou];
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(dist[v] > dist[u]+w[e] && pas[e])
            {
                dist[v] = dist[u]+w[e]; pre[v] = e;
                if(!vis[v])
                {
                    q[++wei] = v;
                    vis[v] = 1;
                }
            }
        }
        vis[u] = 0;
    }
    return dist[T] != INF;
}

double Deal()
{
    int x = INF;
    for(int e=pre[T]; go[e]!=S; e=pre[from[e]]) x = min(x,pas[e]);
    for(int e=pre[T]; go[e]!=S; e=pre[from[e]])
    {
        pas[e] -= x;
        pas[((e-1)^1)+1] += x;
        Ans += w[e]*x;
    }
}

int Check(double ans)
{
    memset(first,0,sizeof(first));  tot=0;
    S=0;    T=2*n+1;
    for(int i=1;i<=n;i++)
    {
        Add(S,i,1,0);
        for(int j=1;j<=n;j++)
            Add(i,j+n, 1,-(A[i][j] - ans*B[i][j]));
        Add(i+n,T,1,0);
    }

    Ans = 0;
    while(Bfs()) Deal();
    return -Ans >= eps;
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            A[i][j] = get();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            B[i][j] = get();

    double l = 0, r = 1e4;
    while(l < r - 1e-7)
    {
        double mid = (l+r)/2.0;
        if(Check(mid)) l = mid;
        else r = mid;
    }

    if(Check(r)) printf("%.6lf", r);
    else printf("%.6lf", l);
}